/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：TrieTree.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-20
Function List ：
Description   ：Trie Tree
******************************************************/

#include "TrieTree.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"

#define MaxCharNum   26
#define EndOfWord   '\0'
#define TRUE         1
#define FALSE        0

struct TrieNode {
    int IsEndOfWord;
    Position *Next;
};

TrieTree Initialize(void) {
    TrieTree T;
    int i;

    T = (TrieTree)malloc(sizeof(struct TrieNode));
    if (T == NULL) {
        FatalError("Out of space!!!");
    }

    T->Next = (Position *)malloc(MaxCharNum * sizeof(Position));
    if (T->Next == NULL) {
        FatalError("Out of space!!!");
    }

    T->IsEndOfWord = FALSE;
    for (i = 0; i < MaxCharNum; ++i) {
        T->Next[i] = NULL;
    }

    return T;
}

void Destroy(TrieTree T) {
    int i;

    if (T != NULL) {
        for (i = 0; i < MaxCharNum; ++i) {
            if (T->Next[i] != NULL) {
                Destroy(T->Next[i]);
            }
        }

        free(T);
    }
}

int IsEmpty(TrieTree T) {
    int i;

    if (T != NULL) {
        if (T->Next != NULL) {
            for (i = 0; i < MaxCharNum; ++i) {
                if (T->Next[i] != NULL) {
                    return FALSE;
                }
            }
        }
    }

    return TRUE;
}

/* Inserts a word into the trie-tree. */
TrieTree Insert(ElementType *Word, TrieTree T) {
    Position P;

    P = T;
    while (*Word != EndOfWord) {
        if (P->Next[*Word - 'a'] == NULL) {
            P->Next[*Word - 'a'] = Initialize();
        }

        P = P->Next[*Word - 'a'];
        ++Word;
    }

    P->IsEndOfWord = TRUE;

    return T;
}

/* Returns if the word is in the trie-tree */
int Search(ElementType *Word, TrieTree T) {
    while (*Word != EndOfWord) {
        if (T->Next[*Word - 'a'] == NULL) {
            return FALSE;
        }

        T = T->Next[*Word - 'a'];
        ++Word;
    }

    return T->IsEndOfWord;
}

/* Returns if there is any word in the trie-tree */
/* that starts with the given prefix. */
int TrieStartsWith(ElementType *Prefix, TrieTree T) {
    while (*Prefix != EndOfWord) {
        if (T->Next[*Prefix - 'a'] == NULL) {
            return FALSE;
        }

        T = T->Next[*Prefix - 'a'];
        ++Prefix;
    }

    return TRUE;
}

// EOF

